Als RSA-Modul wird die Zahl $n= 437$ verwendet. Bestimmen Sie alle möglichen Werte für $e$, die kleiner als 30 sind. Berechnen Sie für $e=31$ den zugehörigen privaten Exponenten $d$. Entschlüsseln Sie anschließend die Chiffrate $c = 89$ und $c' = 98$.

\textbf{Lösung}

\begin{enumerate}
\item $p$ und $q$ ermitteln

Es gilt folgendes:
\begin{itemize}
\item $n=p \cdot q$
\item $n = 437$
\item $p$ und $q$ sind Primzahlen
\end{itemize}

Aus diesem Grund ist eine Primfaktorzerlegung von $n = 437$ notwendig. Führt man diese durch, so erhält man $n = 437 = 19 \cdot 23$.

\begin{center}
\uline{$p = 19$} und \uline{$q = 23$}
\end{center}

Um die Primfaktorzerlegung nicht selbst durchführen zu müssen, kann z.B. \url{http://www.mathepower.com/primfaktor.php} verwendet werden.

\item $e$ ermitteln

Es gilt folgendes:
\begin{itemize}
\item $1 < e < \varphi (n) = (p - 1) \cdot (q - 1)$
\item $gcd(e, (p - 1) \cdot (q - 1)) = 1$
\item $e < 30$ und $e \in \mathbb{N}$
\item $p = 19$ und $q = 23$
\end{itemize}

Zuerst berechnet man $(p - 1) \cdot (q - 1) = (19 - 1) \cdot (23 - 1) = 396$. Anhand der o.g. Punkte ist zu erkennen, dass nun für alle $1 < e < 30$ getestet werden muss, ob sie die Bedingung $gcd(e, 396) = 1$ erfüllen. Die jeweiligen Werte sind in der nachfolgenden Tabelle aufgelistet. Diejenigen $e$, die diese Bedingung erfüllen, sind grau hinterlegt.

\begin{center}
\begin{tabular}{|c|c||c|c||c|c|}
\hline
$e$ & $gcd(e, 396)$ & $e$ & $gcd(e, 396)$ & $e$ & $gcd(e, 396)$\\
\hline 
2 & 2 & 12 & 12 & 22 & 22 \\
\hline
3 & 3 & \cellcolor{dunkelgrau}13& \cellcolor{dunkelgrau}1 & \cellcolor{dunkelgrau}23 & \cellcolor{dunkelgrau}1 \\
\hline
4 & 4 & 14 & 2 & 24 & 12 \\
\hline
\cellcolor{dunkelgrau}5 & \cellcolor{dunkelgrau}1 & 15 & 3 & \cellcolor{dunkelgrau}25 & \cellcolor{dunkelgrau}1 \\
\hline
6 & 6 & 16 & 4 & 26 & 2 \\
\hline
\cellcolor{dunkelgrau}7 & \cellcolor{dunkelgrau}1 & \cellcolor{dunkelgrau}17 & \cellcolor{dunkelgrau}1 & 27 & 9 \\
\hline
8 & 4 & 18 & 18 & 28 & 4 \\
\hline
9 & 9 & \cellcolor{dunkelgrau}19 & \cellcolor{dunkelgrau}1 & \cellcolor{dunkelgrau}29 & \cellcolor{dunkelgrau}1\\
\hline
10 & 2 & 20 & 4 & & \\
\hline
11 & 11 & 21 & 3 & & \\
\hline
\end{tabular}
\end{center}

\begin{center}
\uuline{$e \in \{5, 7, 13, 17, 19, 23, 25, 29\}$}
\end{center}

\item $d$ ermitteln für $e = 31$

Es gilt folgendes:
\begin{itemize}
\item $p = 19$, $q = 23$ und $e = 31$
\item $1 < d < (p - 1) \cdot (q - 1)$
\item $d \cdot e \equiv 1 \tmod (p - 1) \cdot (q - 1)$
\end{itemize}

Zuerst berechnet man $(p - 1) \cdot (q - 1) = (19 - 1) \cdot (23 - 1) = 396$. Man weiß nun durch die o.g. Bedingungen, dass $1 < d < 396$ und $31 \cdot d \equiv 1 \tmod 396$ gilt. Letzteres heißt nichts anderes als $396 \cdot \mathbb{Z} + 31 \cdot d = 1$.

Man wendet nun den erweiterten euklidischen Algorithmus auf $a \cdot x + b \cdot y = 1$ mit $a = (p - 1) \cdot (q - 1) = 396$, $b = e = 31$ und $y = d$ an. Die Durchführung ist in der nachfolgenden Tabelle ersichtlich.

\begin{center}
\begin{tabular}{|c|ccccccc|}
\hline
$k$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$\\
\hline
$r_k$ & $396$ & $31$ & $24$ & $7$ & $3$ & $1$ & $0$ \\
$q_k$ & & $12$ & $1$ & $3$ & $2$ & $3$ & \\
$x_k$ & $1$ & $0$ & $1$ & $1$ & $4$ & \cellcolor{dunkelgrau}$9$ & $31$ \\
$y_k$ & $0$ & $1$ & $12$ & $13$ & $51$ & \cellcolor{dunkelgrau}$115$ & $396$ \\
\hline 
\end{tabular}
\end{center}

Der erweiterte euklidische Algorithmus zeigt, dass $396 \cdot (-9) + 31 \cdot 115 = 1$ mit 

\begin{center}
\uuline{$d = y = 115$} bei $e = 31$
\end{center}

\item Entschlüsseln von $c = 89$

Es gilt folgendes:
\begin{itemize}
\item $c = 89$, $d = 115$ und $n = 437$
\item $m = c ^ d \tmod n$
\end{itemize}

Somit ist $m = 89 ^ 115 \tmod 437$. Die Auflösung erfolgt mit Hilfe der schnellen Exponentiation. Zuerst wird die Binärentwicklung von $d = 115$ benötigt. Ihre Länge ist $k = \lfloor log_{2} 115 \rfloor + 1 = 7$. Die Berechnung der Koeffizienten erfolgt mit Hilfe einer Tabelle.

\begin{center}
\begin{tabular}{|c||c|c|c|c|}
\hline
$i$ & 1 & 2 & 3 & 4 \\
\hline
$g ^ {k - i}$ & $2 ^ 6$ & $2 ^ 5$ & $2 ^ 4$ & $2 ^ 3$ \\
\hline 
\cellcolor{dunkelgrau}$a_i$ & \cellcolor{dunkelgrau}$\lfloor \frac{115}{2 ^ 6} \rfloor = 1$ & \cellcolor{dunkelgrau}$\lfloor \frac{51}{2 ^ 5} \rfloor = 1$ & \cellcolor{dunkelgrau}$\lfloor \frac{19}{2 ^ 4} \rfloor = 1$ & \cellcolor{dunkelgrau}$\lfloor \frac{3}{2 ^ 3} \rfloor = 0$ \\
\hline
$a_i \cdot g ^ {k - i}$ & $2 ^ 6$ & $2 ^ 5$ & $2 ^ 4$ & $0$ \\
\hline
$a - \sum_{j = 1} ^ i a_j \cdot g ^ {k - j}$ & $115 - 2 ^ 6 = 51$ & $51 - 2 ^ 5$ & $19 - 2 ^ 4 = 3$ & $3$ \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|c||c|c|c|}
\hline
$i$ & 5 & 6 & 7 \\
\hline
$g ^ {k - i}$ & $2 ^ 2$ & $2$ & $1$ \\
\hline 
\cellcolor{dunkelgrau}$\lfloor \frac{3}{2 ^ 3} \rfloor = 0$ & \cellcolor{dunkelgrau}$\lfloor \frac{3}{2 ^ 2} \rfloor = 0$ & \cellcolor{dunkelgrau}$\lfloor \frac{3}{2} \rfloor = 1$ & \cellcolor{dunkelgrau}$\lfloor \frac{1}{1} \rfloor = 1$  \\
\hline
$a_i \cdot g ^ {k - i}$ & $0$ & $2$ & $1$\\
\hline
$a - \sum_{j = 1} ^ i a_j \cdot g ^ {k - j}$ & $3$ & $3 - 2 = 1$ & $1 - 1 = 0$ \\
\hline
\end{tabular}
\end{center}

Die Binärentwicklung des Exponenten ist $115 = 2^6 + 2^5 + 2^4 + 2^1 + 2^0$. Anschließend werden die sukzessiven Quadrate von $89$ in $\mathbb{Z}/437\mathbb{Z}$ berechnet.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\cellcolor{dunkelgrau}$89^{2^0}$ & \cellcolor{dunkelgrau}$89^{2^1}$ & $89^{2^2}$ & $89^{2^3}$ & \cellcolor{dunkelgrau}$89^{2^4}$ & \cellcolor{dunkelgrau}$89^{2^5}$ & \cellcolor{dunkelgrau}$89^{2^6}$ \\
\hline
\cellcolor{dunkelgrau}$89$ & \cellcolor{dunkelgrau}$89^2 \equiv 55$ & $55^2 \equiv 403$ & $403^2 \equiv 282$ & \cellcolor{dunkelgrau}$282^2 \equiv 427$ & \cellcolor{dunkelgrau}$427^2 \equiv 100$ & \cellcolor{dunkelgrau}$100^2 \equiv 386$ \\
\hline 
\end{tabular}
\end{center}

Man erkennt nun, dass $89^{115} \tmod 437 = 89^{2^6} + 89^{2^5} + 89^{2^4} + 89^{2^1} + 89^{2^0} \equiv 386 \cdot 100 \cdot 427 \cdot 55 \cdot 89 \tmod 437 \equiv 10 \tmod 437$.

\begin{center}
\uuline{$m = 10$}
\end{center}

\item Entschlüsseln von $c' = 98$.

Es gilt folgendes:
\begin{itemize}
\item $c' = 98$, $d = 115$ und $n = 437$
\item $m' = {c'}^d \tmod n$
\end{itemize}

Somit ist $m' = 98 ^ 115 \tmod 437$. Die Binärentwicklung des Exponenten ist bereits aus der vorherigen Teilaufgabe bekannt und lautet $115 = 2^6 + 2^5 + 2^4 + 2^1 + 2^0$. Nun werden die sukzessiven Quadrate von $98$ in $\mathbb{Z}/437\mathbb{Z}$ berechnet.

\begin{center}
\begin{tabular}{|c||c||c||c||c||c||c|}
\hline
\cellcolor{dunkelgrau}$98^{2^0}$ & \cellcolor{dunkelgrau}$98^{2^1}$ & $98^{2^2}$ & $98^{2^3}$ & \cellcolor{dunkelgrau}$98^{2^4}$ & \cellcolor{dunkelgrau}$98^{2^5}$ & \cellcolor{dunkelgrau}$98^{2^6}$ \\
\hline
\cellcolor{dunkelgrau}$98$ & \cellcolor{dunkelgrau}$98^2 \equiv 427$ & $427^2 \equiv 100$ & $100^2 \equiv 386$ & \cellcolor{dunkelgrau}$386^2 \equiv 416$ & \cellcolor{dunkelgrau}$416^2 \equiv 4$ & \cellcolor{dunkelgrau}$4^2 = 16$ \\
\hline 
\end{tabular}
\end{center}

Man erkennt nun, dass $98^{115} \tmod 437 = 98^{2^6} + 98^{2^5} + 98^{2^4} + 98^{2^1} + 98^{2^0} \equiv 16 \cdot 4 \cdot 416 \cdot 427 \cdot 98 \tmod 437 \equiv 2 \tmod 437$.

\begin{center}
\uuline{$m' = 2$}
\end{center}


\end{enumerate}